#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    public:

    TreeNode* ans1(vector<int>& nums){
        TreeNode* ret = createTree(nums, 0, nums.size()-1);
        return ret;
    }

    TreeNode* createTree(vector<int>& nums, int left, int right){
        if(left > right){
            return nullptr;
        }
        int mid = (left + right) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = createTree(nums, left, mid-1);
        root->right = createTree(nums, mid+1, right);

        return root;
    }

    void frontOrder(TreeNode* node, vector<int>& val){
        if(node == nullptr){
            val.push_back(INT32_MAX);
            return;
        }

        val.push_back(node->val);
        frontOrder(node->left, val);
        frontOrder(node->right, val);
    }

    void midOrder(TreeNode* node, vector<int>& val){
        if(node == nullptr){
            val.push_back(INT32_MAX);
            return;
        }

        midOrder(node->left, val);
        val.push_back(node->val);
        midOrder(node->right, val);
    }

    void show(vector<int> ret){
        for(int i = 0; i != ret.size()-1; i++){
            cout << ret[i] << " " << ends;
        }
        cout << ret[ret.size()-1] << endl;
    }
};

void test(){
    Solution s;
    vector<int> nums = {-10,-3,0,5,9};
    TreeNode* root = s.createTree(nums, 0, nums.size()-1);
    vector<int> ret;
    s.frontOrder(root, ret);
    s.show(ret);
    ret.clear();
    s.midOrder(root, ret);
    s.show(ret);
    ret.clear();
    
}

int main(void){
    test();

    return 0;
}